#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector < vector<int>> result;
        if (!root)return result;
        queue<TreeNode*> q;
        q.push(root);
        bool lefttoright = true;
        while (!q.empty()) {
            int levelsize = q.size();
            vector<int>levelvalues(levelsize);
            for (int i = 0; i < levelsize; i++) {
                TreeNode* node = q.front();
                q.pop();
                int index = lefttoright ? i : levelsize - 1 - i;
                levelvalues[index] = node->val;
                if (node->left) { q.push(node->left); }
                if (node->right) { q.push(node->right); }
            }
            result.push_back(levelvalues);
            lefttoright = !lefttoright;
        }
        return result;
    }
};

int main() {
    Solution sol;
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    vector<vector<int>>aa;
    aa=sol.zigzagLevelOrder(root);
    for (vector<int> a : aa) {
        for (int num : a) {
            cout << num << " "<<endl;
        }
    }
}